package com.le.high.class1;

/**
 * 约瑟夫问题：
 * 1. 环形单链表
 * 2. 数组
 */
public class Problem04_JosephusProblem {

    public static class Node {
        public int value;
        public Node next;

        public Node(int data) {
            this.value = data;
        }
    }

    public static Node getSkillNum(Node head, int m) {
        if (head == null || head.next == head || m < 1) {
            return head;
        }
        Node cur = head.next;
        int temp = 1;
        while (cur != head) {
            temp++;
            cur = cur.next;
        }
        temp = getLive(temp, m);
        while (--temp != 0) {
            head = head.next;
        }
        head.next = head;
        return head;
    }

    private static int getLive(int i, int m) {
        return (getLive(i - 1, m) + m - 1) % i + 1;
    }
}
